스택(Stack)과 큐(Queue)

스택과 큐는 둘 다 선형 자료구조로, 아이템을 저장하고 처리하는 데 쓰이지만, 작동 방식과 용도가 다릅니다. 소프트웨어 엔지니어 면접에서 기본적으로 잘 알고 있어야 하는 내용입니다.

1. 스택 (Stack)

개요

• 정의: 스택은 후입선출(LIFO, Last-In, First-Out) 방식의 선형 자료구조입니다.
  • 가장 나중에 쌓은 요소가 가장 먼저 나갑니다.
  • 접시 더미처럼 위쪽에서 넣고 위쪽에서 꺼냅니다.

주요 연산

• push(item): 아이템을 맨 위에 추가한다.
• pop(): 맨 위 아이템을 제거하고 반환한다.
• peek() 또는 top(): 맨 위 아이템을 제거하지 않고 확인한다.
• isEmpty(): 스택이 비었는지 확인한다.

시각적 예시

스택 (맨 위가 오른쪽):

[Bottom] 1 <-- 2 <-- 3 <-- 4 [Top]

pop하면 4가 나옵니다. push(5)하면 맨 위가 5가 됩니다.

주요 용도

• 함수 호출 관리 (콜 스택)
• 에디터의 실행 취소/다시 실행(undo/redo)
• 수식 분석 (예: 수학 표현식 평가)
• 그래프/트리의 깊이 우선 탐색 (DFS)

2. 큐 (Queue)

개요

• 정의: 큐는 선입선출(FIFO, First-In, First-Out) 방식의 선형 자료구조입니다.
  • 가장 먼저 넣은 요소가 가장 먼저 나갑니다.
  • 티켓 창구 앞 대기줄처럼 먼저 온 사람이 먼저 나갑니다.

주요 연산

• enqueue(item): 아이템을 뒤쪽에 추가한다.
• dequeue(): 앞쪽 아이템을 제거하고 반환한다.
• peek() 또는 front(): 앞쪽 아이템을 제거하지 않고 확인한다.
• isEmpty(): 큐가 비었는지 확인한다.

시각적 예시

큐 (앞이 왼쪽, 뒤가 오른쪽):

[Front] 1 --> 2 --> 3 --> 4 [Back]

dequeue하면 1이 나옵니다. enqueue(5)하면 뒤가 5가 됩니다.

주요 용도

• 작업 스케줄링 (프린터 대기열, CPU 작업 큐)
• 그래프/트리의 너비 우선 탐색 (BFS)
• 웹 서버의 요청 관리
• 데이터 버퍼링 (입출력 버퍼)

비교 표

스택(Stack)과 큐(Queue): 구현, 사용 사례, 시간 복잡도

스택과 큐를 어떻게 구현하는지, 주요 용도와 계산 효율성을 알아보겠습니다.

1. 스택(Stack)

A. 구현 방법

1. 배열을 이용한 구현 (Java 예제)

class Stack {
    private int[] arr;
    private int top;

    public Stack(int size) {
        arr = new int[size];
        top = -1;
    }
    public void push(int x) { arr[++top] = x; }
    public int pop() { return arr[top--]; }
    public int peek() { return arr[top]; }
    public boolean isEmpty() { return top == -1; }
}

2. 연결 리스트를 이용한 구현

class Node {
    int data;
    Node next;
    Node(int d) { data = d; }
}

class Stack {
    private Node top;
    public void push(int x) { Node n = new Node(x); n.next = top; top = n; }
    public int pop() { int val = top.data; top = top.next; return val; }
    public int peek() { return top.data; }
    public boolean isEmpty() { return top == null; }
}

3. 내장 라이브러리 사용

• Java: java.util.Stack 또는 Deque<Integer> stack = new ArrayDeque<>();
• Python: list의 append()와 pop() 사용 또는 collections.deque

B. 사용 사례

• 함수 호출 스택(프로그램 실행)
• 에디터의 undo/redo 기능
• 수식 평가(예: 수학 식 파싱)
• 브라우저의 뒤로/앞으로 가기 네비게이션
• 그래프/트리의 깊이 우선 탐색(DFS)

C. 시간 복잡도

2. 큐(Queue)

A. 구현 방법

1. 배열을 이용한 구현 (원형 큐 예제)

class Queue {
    private int[] arr;
    private int front, rear, size, capacity;

    public Queue(int cap) {
        arr = new int[cap];
        capacity = cap;
        front = size = 0;
        rear = cap - 1;
    }
    public void enqueue(int x) {
        if (size == capacity) throw new RuntimeException("Overflow");
        rear = (rear + 1) % capacity;
        arr[rear] = x; size++;
    }
    public int dequeue() {
        if (size == 0) throw new RuntimeException("Underflow");
        int item = arr[front];
        front = (front + 1) % capacity;
        size--; return item;
    }
    public int peek() { return arr[front]; }
    public boolean isEmpty() { return size == 0; }
}

2. 연결 리스트를 이용한 구현

class Node {
    int data;
    Node next;
    Node(int d) { data = d; }
}

class Queue {
    Node front, rear;
    public void enqueue(int x) {
        Node n = new Node(x);
        if (rear == null) front = rear = n;
        else { rear.next = n; rear = n; }
    }
    public int dequeue() {
        if (front == null) throw new RuntimeException("Underflow");
        int val = front.data;
        front = front.next;
        if (front == null) rear = null;
        return val;
    }
    public int peek() { return front.data; }
    public boolean isEmpty() { return front == null; }
}

3. 내장 라이브러리 사용

• Java: Queue<Integer> queue = new LinkedList<>(); 또는 ArrayDeque<>
• Python: collections.deque, queue.Queue

B. 사용 사례

• CPU 작업 및 스레드 스케줄링
• 운영체제의 프린터 대기열
• 그래프/트리의 너비 우선 탐색(BFS)
• 생산자-소비자 문제, 버퍼링, 데이터 스트리밍
• 서버/웹 어플리케이션에서 요청 처리

C. 시간 복잡도

3. 요약 표